package com.atguigu.linkedlist;

/**
 * 环形链表的实现---------约瑟夫问题
 * @author WangJX
 * @version 1.0
 * @date 2019/9/22 23:21
 */
public class JosepFuList {
    public static void main(String[] args) {
        CircleSingleLinkedList list = new CircleSingleLinkedList();
        list.addBoy(5);
        list.showBoy(list.getFirst());
        int countBoy = list.countBoyNum(list.getFirst());
        System.out.printf("环形链表中节点个数为%d \n", countBoy);
        list.countBoy(list.getFirst(), 1, 2, list.countBoyNum(list.getFirst()));
    }
}

class CircleSingleLinkedList{
    private Boy first;

    /**
     * 添加环形链表数据
     * @param num   环形链表的个数
     */
    public void addBoy(int num) {
        if (num < 1) {
            throw new RuntimeException("输入的数字不正确");
        }
        Boy temp = first;
        for (int i = 1; i <= num; i++) {
            //判断是否第一次添加
            if (temp == null) {
                first = new Boy(1);
                temp = first;
            }else {
                temp.setNext(new Boy(i));
                temp = temp.getNext();
            }
        }
        temp.setNext(first);
    }

    /**
     * 打印环形链表
     * @param first 环形链表头
     */
    public void showBoy(Boy first) {
        if (first == null) {
            throw new RuntimeException("链表为空！");
        }
        Boy temp = first;
        while (true) {
            //如果下一个为头节点，代表已经循环到最后一个节点
            if (temp.getNext() == first) {
                System.out.println(temp);
                break;
            }
            System.out.println(temp);
            temp = temp.getNext();
        }
    }

    /**
     * 统计环形链表中节点个数
     * @param first 环形链表的头节点
     * @return
     */
    public int countBoyNum(Boy first) {
        if (first == null) {
            throw new RuntimeException("链表为空！");
        }
        Boy temp = first;
        int sum = 0;
        while (true) {
            //如果下一个为头节点，代表已经循环到最后一个节点
            if (temp.getNext() == first) {
                sum++;
                break;
            }
            sum++;
            temp = temp.getNext();
        }
        return sum;
    }

    /**
     * 根据用户的输入，计算出小孩的出圈速度
     * @param first 环形链表头节点
     * @param start 从几号id开始
     * @param countNum  计数的个数
     * @param nums  环形链表的节点个数
     * @return
     */
    public void countBoy(Boy first, int start, int countNum, int nums) {
        if (first == null) {
            throw new RuntimeException("链表为空");
        } else if (start > nums) {
            throw new RuntimeException("开始的数字大于链表的节点个数");
        }

        Boy temp = first;
        Boy helper = first;

        for (int i = 1; i <= nums + start - 2; i++) {
            helper = helper.getNext();
        }

        //first指针移动到开始的boy
        for (int i = 1; i < start; i++) {
            temp = temp.getNext();
        }
        //计数出队列次数
        int sub = 0;
        while (true) {
            //判断是否输出了最后一个节点
            // 当出列的个数等于boy队列的全部个数后，就认为循环完毕，停止循环，否则最后一个会成为一个死循环
            if ( sub >= nums) {
                System.out.printf("幸运者是：%d \n", temp.getId());
                break;
            }

            for (int i = 1; i < countNum; i++) {
                temp = temp.getNext();
                helper = helper.getNext();
            }
            System.out.println(temp);
            //出队列一次加1
            sub++;
            //清空出队列的节点，最后一个节点会形成死循环
            helper.setNext(temp.getNext());
            temp = temp.getNext();
        }
    }


    public Boy getFirst() {
        return first;
    }
}

class Boy{
    private int id;
    private Boy next;

    public Boy(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "id=" + id ;
    }
}
